#!/usr/bin/env python
# -*- coding:utf-8 -*-
# @Author  : 1230
# @Email   : xjh_0125@sina.com
# @Time    : 2020/1/10 17:08
# @Software: PyCharm
# @File    : l424_characterReplacement.py


import bisect


class Solution:
    def __init__(self):
        """
        给你一个仅由大写英文字母组成的字符串，你可以将任意位置上的字符替换成另外的字符，总共可最多替换 k 次。在执行上述操作后，找到包含重复字母的最长子串的长度。

注意:
字符串长度 和 k 不会超过 104。

示例 1:

输入:
s = "ABAB", k = 2

输出:
4

解释:
用两个'A'替换为两个'B',反之亦然。
示例 2:

输入:
s = "AABABBA", k = 1

输出:
4

解释:
将中间的一个'A'替换为'B',字符串变为 "AABBBBA"。
子串 "BBBB" 有最长重复字母, 答案为 4。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/longest-repeating-character-replacement
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
        characterReplacement  正确 时间复杂度高
        characterReplacement3 正确 On 滑动窗口
        """
        pass

    def characterReplacement(self, s: str, k: int) -> int:
        if k + 1 >= len(s):
            return len(s)
        pre = s[0]
        count = 1
        li_char = []
        li_count = []
        for i in range(1, len(s)):
            v = s[i]
            if v != pre:
                li_char.append(pre)
                li_count.append(count)
                pre = v
                count = 1
            else:
                count += 1
        li_char.append(s[-1])
        li_count.append(count)
        if k == 0:
            return max(li_count)
        res = li_count[0] + k
        tmp_index = 0
        for i in range(len(li_char)):
            change_count, j, tmp, joinNext = 0, i + 1, li_count[i], True
            tmp_index += li_count[i]
            if len(s) - tmp_index < res:
                break
            while j < len(li_count) and change_count < k:
                if li_char[j] == li_char[i]:
                    tmp += li_count[j]
                else:
                    change_count += li_count[j]
                    joinNext = change_count <= k
                    change_count = min(change_count, k)
                j += 1
            tmp += change_count
            if j < len(li_char) and li_char[j] == li_char[i] and joinNext:
                tmp += li_count[j]
            if change_count < k:
                tmp += (k - change_count)
                # print(111, li_char[i], i, j, change_count, tmp)
            res = max(res, tmp)
        res = min(len(s), res)
        # for i in zip(li_char, li_count):
        #     print(i)
        # print(len(s), len(li_char))
        return res

    def characterReplacement1(self, s: str, k: int) -> int:
        if k + 1 >= len(s):
            return len(s)

        def get_len(li, k: int) -> int:
            res, tmp_k = 0, k
            for i in range(0, len(li), 2):
                tmp_res, k = 0, tmp_k
                for j in range(i, len(li)):
                    c = li[j]
                    if c > 0:
                        tmp_res += c
                    elif k >= 0:
                        tmp = -c
                        tmp_res += min(tmp, k)
                        k += c
                        if tmp > k:
                            break
                    else:
                        break
                if k > 0:
                    if i > 0:
                        tmp_res += min(k, -li[i - 1])
                    else:
                        tmp_res += k
                res = max(res, tmp_res)
            return res

        res = 0
        tmp_s = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ'
        dic_sum, dic_index, dic_count = {}, {}, {}
        for char in tmp_s:
            dic_count[char] = []
            dic_index[char] = []
            dic_sum[char] = 0
        pre, count = s[0], 1
        for i in range(1, len(s)):
            v = s[i]
            if v != pre:
                dic_index[pre].append(i - count)
                if len(dic_index[pre]) > 1:
                    dic_count[pre].append(dic_index[pre][-2] - dic_index[pre][-1] + dic_count[pre][-1])
                dic_count[pre].append(count)
                dic_sum[pre] += count
                pre = v
                count = 1
            else:
                count += 1
        dic_index[s[len(s) - 1]].append(len(s) - count)
        if len(dic_index[s[len(s) - 1]]) > 1:
            dic_count[s[len(s) - 1]].append(
                dic_index[s[len(s) - 1]][-2] - dic_index[s[len(s) - 1]][-1] + dic_count[s[len(s) - 1]][-1])
        dic_count[s[len(s) - 1]].append(count)
        dic_sum[s[len(s) - 1]] += count
        for key in dic_count:
            if dic_sum[key] + k <= res:
                continue
            tmp = get_len(dic_count[key], k)
            res = max(tmp, res)
        res = min(len(s), res)
        return res

    def characterReplacement2(self, s: str, k: int) -> int:
        def get_index(s):
            tmp_s = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ'
            dic_sum, dic_index, dic_count = {}, {}, {}
            for char in tmp_s:
                dic_count[char] = []
                dic_index[char] = []
                dic_sum[char] = 0
            pre, count = s[0], 1
            for i in range(1, len(s)):
                v = s[i]
                if v != pre:
                    dic_index[pre].append(i - count)
                    dic_count[pre].append(count)
                    dic_sum[pre] += count
                    pre = v
                    count = 1
                else:
                    count += 1
            dic_index[s[len(s) - 1]].append(len(s) - count)
            dic_count[s[len(s) - 1]].append(count)
            dic_sum[s[len(s) - 1]] += count
            return (dic_index, dic_count)

        def get_count(li_index, li_count, end, begin):
            index_end = bisect.bisect_left(li_index, end)
            index_begin = bisect.bisect_left(li_index, begin)
            res = sum(li_count[index_begin:index_end])
            # if index_end == len(li_index):
            #     pass
            # elif li_index[index_end] != end:
            #     if li_index[index_end] + li_count[index_end] >= end:
            #         index_end -= 1
            #         res -= li_count[index_end]
            #         res += (li_index[index_end] + li_count[index_end] - end)
            return res

        if k + 1 >= len(s):
            return len(s)
        tup = get_index(s)
        if k == 0:
            res = 0
            tup = tup[1]
            for key in tup:
                if len(tup[key]) > 0:
                    tmp = max(tup[key])
                    res = max(tmp, res)
            return res

        res = k + 1
        for i in range(0, len(s) - k):
            tmp = 0
            if s[i] == s[i + 1]:
                tmp += 1
                continue

            # start = tup[1].get(s[i])[bisect.bisect_left(tup[0].get(s[i]), i)] - 1
            count_c = get_count(tup[0].get(s[i]), tup[1].get(s[i]), i + k, i)
            count_c = min(count_c, k)
            tmp_res, j = k + tmp, i + k
            while count_c > 0 and j < len(s):
                if s[j] != s[i]:
                    count_c -= 1
                tmp_res += 1
                j += 1
            tmp_res += count_c
            while j < len(s):
                if s[j] == s[i]:
                    tmp_res += 1
                    j += 1
                else:
                    break
            res = max(tmp_res, res)
        res = min(res, len(s))
        return res

    def characterReplacement3(self, s: str, k: int) -> int:
        dic = {}
        res, l = 0, 0
        for r in range(len(s)):
            dic[s[r]] = dic.get(s[r], 0) + 1
            max_letter = max(dic, key=dic.get)
            while (r - l + 1 - dic[max_letter]) > k:
                dic[s[l]] -= 1
                l += 1
                max_letter = max(dic, key=dic.get)
            res = max(r - l + 1, res)
        return res


if __name__ == '__main__':
    sc = Solution()
    s = 'CCDAEEEDDEBCCDBACFCEDFAECCCCFDEADFECCDEBBEAFEBEEAFDEACBCECEDFBBDECCAAFCDDCABDBAEFABCBAEDCBFAAECEECAEABCBCCABAABECAFEAACEEBCFFFDDCDBCDCACCFFBDBEDBDEDFFECDBDBDABBBDAEACEDFBBAFBABFAEBADCEFDEAFCFDDFFCAFAEEAAEEECBFADCEFADAEEADCBACCDDEFCCCACEBCCEEDBBFFBCEDEFEACBDBBABDCBADDFEADCBEBBCFBCBAECECCCDDADCDBEAFCEADEBBFFACEAAFFDDCEFEEACDFDACFCEAFDCABBBBEBEBDDABEDCAEFCBFEFFABBCFAFCCBDECDBCABFABFABEECEDFFDFFDEBDBBBEEAEFFEDBADAABEEACFCCBEDADFCBDBDDBDCABDFCDECEFBFDFCDCFEBCCDDFABCBBCCCBCABEECBCBCBEADECAFFFCFAEFFFCDADBADFDFFDCBABFADFAAEFBADCCAFEEBFCFEBCFCEDACCADAAEEEBDCADABFBADBAECACBEFAECFFBCFBDEAECEBCFFDCEEEEEAFEBFFAEBBBDBBFFDBFADEECFDEBDBBCEEDBBADDBBDEDDAFEBCEDCAEBEEEDCFEDDACCDDCAEFDECBDCBBEFCFCECAABCFBBACACCEACDCBDBFECBDFFEBBFBABDECAECAFEEDAABEAFBECAACCACEEAADCEFEEBFFCCBDBCCBADDAAAADBFAECFBFACFDECFACDCCBBCADAEBEDDEEDCBDAFDDAAAFECDADBDAACCBDFAEEACFBBDEDDCCEAAEFEBFCAAEDDCFBDEFECBEFACCCDEDAAABEDAECDEEFCDACCBCDFBCADBCFAACCBBDFFBFBCACEABACAFEDCECCBDFAEDCBDCBAAFEDBCCBBFAFAEABFBEEBDCDFECDDDBDDCCBEFCCEDCECFCBEFFFBFBFBFDDCBEDADECCFFAFAEBEAABECFECABDABFBCEDFCCCCADEBCFBECCDFAAFEFEADACDEFFCBACAACFFECAAFDEDECCDFEDADBDAECDFFECAFFFEDEBEDBBBBBABDAEFFFDDDDCCEEEADEBFEAEFDACBFDBFDADEEACECFADACEEDBCECBCEFCBFBDEADAFCDACCFAEFEFAFDFECAABACFFFDCCBBCCDFECEDECDFDBBFACCDFBADFABBFADDFFCAAABEBDFAAEDAACFCCAEECCAFCEEBEEBCCFFEFFDEFBEEFBBFECFADAFFEBAAFBCFBAFBACDFDAEDBEBEEBBFDEDCEFCBBBABCDAEBEFAEBEAFDECABBADBFCEFFFDBAFDBBEBBCAACBFDDCEFEEEDDADBCFCEAACDBFBFDEACDCDFABDACBCAEEDECCDBDBCBACEBBBBADCBFCDDBDFECEECFDFFBDCBAAEBFCFCDFDBBBFCDECBADAFCBFECABACBFDBAFDCDBBBECCDFDFBECEDBCCAEFDAFACEBFDBDFAFCFFACABCAAECCBBEEBDAFAEFFFEBDECBEAECEAECACDBCFEAADBFEADCCEFAFCAADAEEDFBAFACBAFCEACAADDECFBFDBFCCFAABDABFBEEDFDBAFFECBDDCDCBDEBEFDCCBDBFECBFEAFDCDECAFEAAEAABDFDBBFECAECFEBADCFEEDCBDBFDBBECECFBDDBEFAACEABEFCAAFBDACDDFAEEFDAACBEAEAFDAFEECEFECFBABABBCCBFECBBCAFDCEDCBCAEBFBBCCCBBAEFEFBEEDEFCABEFEECCFBAADEFCEFDDDEDDDBBDABEEFECAEEBCCDDFBAEDCBCCEFFBECFBDECAFEEDBECEBACEBFCEFBECEDFABFAADEBACECDEEBDDFAAEFCCFBFCCAEAAEFAEDEEFBADFCDCFAFEDBDADCFFBDBBEDFEDEFDFCAAAFBADDBDCCCCACDDBBFBECCACDAACCBBDFEEBAACAEDEBBDCDEBDADCAADEFFDDAEADDDFBDBAACFDCEEAAAFDEBBFFEBACADCACDEECCCABFDDCAADEAFABCCCEEFEDDDCBEEFFEDFBBAECDEAAADAECEAACBCBBFCFBEEAFFFDEFDDCBDDDAFAFDEBCEEEACACACCBBBCBADDCECBDEDAAADEFDDDEAEBBBEAEFEEBEAABCFCBCAFDCFDDCFDFAABEFCAFEFADBCDDEADEFAFDAFDECBCECEADFCDAECBDBFEAEAACEBFFFAFEEDABBEBCCBAFACEAFFFABCAEAFEDFCBFEAAEDCCBDBFEFFFCDEAEBEBCDCDEEFDBEEAFBBAEEEAABBEDBFACFCACFABAEBAFADBBEBCEBCFECBFDABBAAEDCDECEAADEDBBFAEECCADFCBAFAAFEDAEFDACBDEAABFFAACEFDFCFFCEFACFBDDABCACACDACACDEBACDCDCADEADFBFACEAABCFDCDDAAEFCFEAFCFFAFDCFDEDAEFCEDAFDFFFBECCFEAADEFAACFDEFBEEBCDADDFCDBADBADFFCCCFBBBDDDEEADDADEFDDECFFACCDFCCBBFACFDFBBEFBCEDACACBAECDECBCBCCFEBEEAEECDCDBAADEABFFCFECBBEFACDBFEBAAFBBDFDEEFCCCFEBBBFECCEBDBADBFCDFCDBADCEACCBDCBAAFEEDDFEAEDFEEEEBCAFCDDBCBDDDCABCBFDCBEFCBCEBFDFBCCDBEAABEAFCACDEBEDCAADEDDFFBFEDAFEFACDDCAECEAEBBECBAACADDCBEAFFBCFAFBBAFCDDCEBCAEFEFBABFCBFDDAEFDBFCDFDACFAAAFCECEAEDDBFFBBBEBAAAAADABEDEEBCECCBCBCEEBECDCFDCCDEADFBDACAFFAADCBDAEEABEDBBADAEFCBBAEFEDBBFEAADFAFBABADBBDCDECCDAEBFACDDEECEEBEFFBCEAEDEBDEACCFAEDDDFADCCFDFACFECEFDDCCEECBFDABDFDCBEDDABEFFCDDEDCEBEFAEBFCFBEACCDABDDACBEFBCFCEEEEFEBABBEFCAEEECEBBDBEBDDABEBCCABCFFCDBBAEBBFAABCEBADCCEEADBBEBCCDBAAAFBFBCFFACCFFFDDBFAAEBACACFEBEDACAABAEECFCAABCDABBCEDADFFAABBDDBFDCFEEFADBCCBDAAFCFCBEAECEBFFEDDFCBCCFDEEAABCDFEBFEACDAFCCDCFBCDDAEDFBAAFBCDFFBAAFBCEFAFCBEAEECEDDBBDFFDAFBBFFECAFDAAFDCFDCBBBFCEDCFADFAEEDFEFDCCACACAACCBAEDFDDBEECFDEBFCACBDACBAFFCCEDBBEECBACFCDBEEBAADBCABCFFAFFCBABDBEBCDDEEDEBBDECAEEEBFFFEDFDFECEAFAADDAEAAAACBBDFFACAFFEEFAECDDFDBCBCDEFDFFDDACEEBBFDBBEBAEFDACEEEACAFACCBDFEABEDCADFCFFEEBFFBFAEAFBDEDABEACADEACDDADCCFBCDBFCBDCADBFBBBFECCCEBFDEDEEDBCDCBEEBCEFFEADDFDCABAAEAFCAEACCBDFCEECDCFCABCCDDAFDFACCCFBDCFFFDDBAFCECCCBFCAECABCBFEEDADCFFCFBDAEEDBCABBCFFDBCECBAABEEFFDDAFDEBAAFBDBDEEBACFAEBEECFAEDDFDBBFEDACBADECEBCFCCFCCBEEEBCCFFFEFFAEDBECAFBFBFDDFEBDCECAFFCCBAECCAAFEDDDAFAABADBAFEDAFFEEAFFFBEFBEADEDDFAFEBDFAEBCDDFBCFEEAFDDAAFAAEACBCEACBCBEECFAAEFBBBEFDBBDDCEBBABFEFCABEBDAFDDDFDCCFFFECDFACCAABCDABDABFFBACBAADDCEBBBDFEEFAAADEEEFEDDDFCBCDFDFEFCEEFCBCAEFFCEDAADBDEFEABBEEDBFBECDCACAACCAAAFCEFBBCCEADBFBCFCCCEFABBDADBACACDABBADAFDECFBDABDEBEBFDFCBADAEDFCFFCEDEBBADFDBCFFBFAFDCFEADFFAEDFEBDCCEAABDBDCADABACCAAFEDDFCADAFDFADDCEEAFAAACAFCAAAFEBDBEBACCABCBFCCBCEDADAEAFDAEFDEABCACCCECFDFFCAEBCECAEEDFFEDAEFEBCAAECCFBDDACABCBCEBBADCDDECDBBEFAFCDAFBEDCEDBAEBCADEDFFEECEFDDEFCBBBBEDBBBBCBAEFDDEBDBCCEAAAFADEFACFBABCCFDCBBADCBAEEEEBAEAFCEEFBCFCBFEFDDCBDCDCEAFEAADEEADAEFBBEDBBCECABFCCEBADECACDAECEBECBAAFCBEABCBDFECDECFDBAFDBCBDFEDBEACDBDEBEABFBBEDDBAFBACCDEABDBEDEEFEDDDCDACEBEDBBBFBEFFBCAFBAFFAEAFACCFDFDFCBCDAABDFBBECBFFAABCFCFCAEEBFCCDFFEFEADBCDDDFCEDBFEABDDFBCBEABECBCCACCCCABAAFCABCAFFCCCFCBBEFEEBEECEEBDDEBABAFFEAAADACDFDBEAABFAECADAEBFFBECBEBCEEEBFEAECEEFAFAEFCDECDECFEBFFBAAFADCAAABDBCDABCAAAFBAEDEFFEDABCDBBECBCCDEFBDACFFBFCEAEFBDCADAEEDCBFEDAEEDBBFFFCFEDFDDAADDCAECBBECDDDFBAFEABFDBBBEEDBFAFAADFDCFCBEAFAEBBDDFDFFCBBCFCCBCCEBAFBAFDEAFCAFFCBDDABDFDBAFDEADCBDFCAACAEEFDEABAEDAFBBBFDACBDABFBFBEAEEFEFCCDCECAECECEABBEFABDFAFDABBDFEFFCBDFCFFEEBBFEDFCADDBEADFFDDACCDCDEBADDABBDADAFCACAEDFDFFDCABAABCCEBDEAFBDCBECFFCAAABBECDBFDFBDEDCACDEAADCDFEAEBBBADFECECEAEBEBFDCABEDDBEECEEDFCEDDADAEBCEEDBAFDFACDEDDABDEBDDDAECBFEFCEEDBBBEBADFFCABDFABFBBFCABFFCCADFCBFBABCDFFDCFBACBCCBBDCDCABFDAFBCFAFBDAFAACBFACCCDBEDFADFEEEDCADEFFFDDCECADEFCDEDCCDDFEDFEBCBCABDDFEADFDFFECFFCCBCABEFBDBDAEDACBBFFBDFEEEACDEBDFFCDEFEBFBBEFABBDFDADDBACEEEBAEECEDACCCDDDFBCEEECCDAEDCCCDBCEBDDADAACCFAEEDFBAEECACFFDEBADDDAABBCDACEEBEAFCADEAFFDBAFFEDAFECCAAEBAFACACEDEBCFFFFDEDDEAFEBCEFDCBCBCBCCBADBAACFDFFBFDABDACCBFEEADFECBBCAFCFDADAACFDBAAAEEACCDAFFCFBCAFBDBAECCCFBDFBFCEBEABFEADAADAEAABEDDACBCCDBAFCCFEAAFBBBBFFCBADEBDECFCCADDCCFFBEDCAADDDFDCFBABBEBBFFDDDBCDBCDDAEDFDBCADEDDECBAAAFCDACDEAAEFEACEBCEEAEBEFCEDEDCAAAFBFCDCEFFBCFDCBAFEDACCBFFAFCBADAEFDBDFAABABDCDABDEAAFEBFFCFABBDECEDDBECEEACCDBEEAEBEECDBBBDEEADFDEFDADDBAACBCCDCCFCFEFEBCDABEFBABCDCBFDAACDDFCCFACEBDCFEABACFEBAFECEAABFFDBFFFDACEAECBFDECFDAFCECEBCBFFAEDBEEDFDEBBBCFFEBFFDDCDBDFCCBADCDDBDEACEEDDBECCEFDAFEAABCEDFAEAFCEFDAAECEFDEDDBACDBDFCAECBEFEDADBBBDFFADDCCADBFBAECBACDDBEFDCEDBCFDDFCAEDBCBBDCFBDACFBBEEECFCEBFCFDCAACBBEBEACFCCECCCEFEAEBEBADDACCFCFBCADEEBCBDBFAAFEFBFBBAFAACDDFFBDCECAABEAADAEDCECDEDADFBEACDBBEAACDAABEEDBDADCACFEEABBCBFEDDCDBFDCADCABBECBBCCBDBFEBEBFCCEDBFABDCFFFECFCEEFFBECCCAAFBCBDBDDADCFCEDBEEDAEBCABDFEDFACBFCBEABEFCDBDCFACBBACDFEBCCDBBBCFEADACAEDCCFEAECDAACAFFDFFABFBDCBAEBABDBCFABAAFEFECBAFBCEDCFEAFEDCBCCDDDCEBDFADCEEBABBFAEEACADCABCFAFBBEAFDFBDABBCECAEFEDACCCAEFFACCDADACCFAFEBABACFEFACCAACFFFDCDDDADCEEAABEEBBEFFFBFEECFEBCBFDEBDAAFCBFABFFCBDBDEADACEACBCDCEEFABAFBDDADDADDDAEBDDABBEAFDEDFDACCCFEBCACDDEFBBDACCBCACBDFFCFAABEFFDBFAFDADBDFEFABEFFFCBDEBFDBEECDACFEDCBFDBFEABEEEBADBADDFEAECBCEBAEABBBEEFDCEFBDEADCFBBAFEACBDEDAAEBDABBAAFCBDEFDEABCAFCDECABFDAFBEEDDECBCABBACFEBBACEEEFADEDECFBABECECEBCABAAFBFDADFDEDCBEEAEEAFBFFCCAACCEBCBEEBBABBDAEBDBBEFDEDCABEAAADFCDFDEDFBFDFFDEEEBEACBDDDFDCACAAABBDBFDCDEDFDDFBDDABEFFBCCDFFAFAACCEACEFAEFFCBBEECCBDEADCDBDADEACBFFDFDFDACFDABBEFFDFEDEDEEACDFEEBFCBBDADAEEFFFBFDACBFDBBBDDDDCDFECBDBFAFDEEEDBFDBDEFAFEFDACBEDDAAEBEDCFCABFDAADFEFBACCEBEECECDDBCCDECFEABABEEDDAEBEDCEBABEBBFAEEBCEDEFCDBEEBBCBCEEEEFFFFEDFABFBDECFFFDDBDFCCDBFFDDDEDEBAEFABFCDEDCCDEBBAECCAEEFFFEFCACACDEECBBBBEFBAEFAAFBBCDABEDEEECBDDCFEDAFCFFEAAFEEFBFDCBDDEDBEFECBDFEBFEBDFDEEBCAEBDFDFAEAACEADCCECDECCDFAAFBCEDFEFAEDCFFDAECDAAEBEFEFDCBDCCDCDADBEDECADBBCBEBBABEDEEDEDBBAABCCBBABADEADFCCFDBCACAAFAFCDDFDFFAAAFDFFBDDEFAFFFCAEEEFFACECEDDEDCEFACFEDBDDFABEBFCEBECFFACACAFFBDBCBDBFCEFBDFBEFAEDFCFBCDCCABFEABECFCACBEFFAEAAAEDBFAAEDECBBBEAFDCACDCFDAFCECBCBCCEFFDCACDEEADAADDACCDAFECDFAEEFCDBAEAFFCDBADDFAAFACFEDDADBDFECAECBCFCAEACDDFEABFFEDADCECDFADFCBDFAFCFFEFECABACADCFCCFCDFDFBBCEFDACBBCCDDBADEDDFBACFFAFBBFBECBCCFEBCFABBBDCCCBDBEBDDCBBDFDDBEFCDADAECDEBFDCEDEBBECAABABEDAAECAEEFFDDFBCADCFFCAFCFECFCEBFDECBEEBCCFCCACFAFEBBADAEECCEEECBBDAEEEDCCDCECAEFBAFDABBECFDFBDEFDFAFDEABEFBAAAACCEAFEFABAAEEAAFABFAACBDCCBDFCEBBECECFEBCEBEFACCFEEBDBAEBDAAFBFFBADADECCABFEEABADEFBBFFEFCFFDEEDECAECABBBAFAFDCFCDADACACDDDBFADBDCEADEAAAACDBDADCCEEEBBFADAEEEDABDCEACBBEFEFEADBDEABEEFABDAFBFAEBBDDFCECECDFBEBFBFBCCBABBBAFDBECBADBACDBAACDEBDFFEDEBCACACADBCFEEDDCFBCABACAADCDAAFEADEDDBCCDFFFCAEAFBEBBCEFCEABCCEBBAAFCCDDFDEBEAECEEADDADFDFADDAABDCADEDDAACFCFADDCEDBDCAEFACFBDADECCCFDEFFDCADDEAACFCCEADCAEECCBAABFBDFADDDBBFDDCAEDDBFCCEBFADFBAFCBEECEAFBFADEBCCADCAAEDCCCFACECDADFAEDEBDDAADBBEECEEFEFEEBDBBBACBBBEEFECEFDAAFEDECCAEABCBCAFBFABFBAFDCDEFDDFFCADBDABFEFCCBDEEFBEDDBABACABBAABCBCBCEDAAABFABFDFAACCFDCDFFCFBAFCFDECEBBBBCFEAFABDEDEBECCCDBEABAAAFFEBAFAEDDBEFAFCBAACCABDCCCEFADFCAEFBFABBBECFCCFDCFDDCECFFCBDACCDACDEAEDFCDADCDDCEBCBEBDDAEBBEDDDCBBEBADECCFEAABFDDFECCCCCDEADFBAACCBAEADBDADFABCDDCECDFEDBFFBDFDAEECDBBAABAAFBECFCDDCBFDBFACDBACAFEBFBFFEEDBEABEFEBABDFBBDDEDFABBDBFAFBEAFAEDCABCFCDEFABAFDDABBDAADCEBACEAEADBEBCBBDAFABCEEEADFCABFFCBFCBACEBEACEAABDCCAFFDABFADDCFBDDAFFABAEDADFFBCBABDCDEACCDAAADEAEDEBFDDBADDBACDEABFFCAEBEBDCFDABACECFBBFBEACCDACBDBCEECFFAECEBADEDDFBEEACECBAFDBFFAFBBDCCCEACEEACFABECDBBAAFCDABFADFFACCFDECAFDCEFDDBDFBAFAEBEFEADFCFBDEBCACDBEFDEBAACCADFDDFEDEABBDDAEEADEBDFEBAFDCBCBABCDBAFBCDDEEDDCCEAFFCCADAEDFCAFABEDFECFBBAEEABBDBECCCCCEABFFFBBBFBEDDDEAFFFEAEFFDAADDEABEDDFDBBEFABFECFEECCCCDBAECFCEACEDEBAFCCFDEDCFCCDBDEBCCFBFACCDDAFFBCDEAFEEDCDABBFEAADDECDBFBBFAEDAACABEFFFFECFADEEAEDEEEDFFBCBFABEDABBDBBEDBFEEAAACFFDBBDEEBBBDDDCCEBBCDDFEEFDFBFCBCEFEDCEFFECCBDEEFFECABFACBFCFFEFAECDEABAFECEDEEBAFBBCFFBDAACFBCBFBEFABBBCECCDAACBFBAEABCBBEFEFCDDBBAEFEFBDBAECDBCEAFECEDDECAFAEABCCEAAEACEFFFADDCDEBFDAAACFCCEBEBABCFBDDEECEDBFFFADBDFABDFFCEDCAAEFCDCFECBBCCCDAAABDBAECBABDABEAAFABBFFCDECFCAEFCAFEECBFCAEDCFFDBBFDEBBCBCFBFFFFFECDBEFDEEDFBAFADBBBFFEEFFECFEEEDABBCBDEDEFDCBEBCCAEFFADDAAECCEFEFCFADBAADAFDEBBEECABDEEDCEBCABFBCECDDCCDBBABDABCEDBDCBBDDACECBDEFBEEEEBACBBADFDBACDCDCEBFDEBDAAFCDDBCCCBACAECCAADFBCBACBFBDFFCCCAFBBBBACEFABBEFAAFFDCEEDDDDFBBBADDEEDFBFADCDBDAAAEEFAFFAFCAACFCCFFDAFFCCDCECDEBADACCFFEBCAFAAFBB'
    k = 4567
    # s = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ'
    # k = 5
    # s = 'ABAB'
    # k = 2
    # s = 'AABABBA'
    # k = 1
    # s = 'AABA'
    # k = 0
    # s = 'IMNJJTRMJEGMSOLSCCQICIHLQIOGBJAEHQOCRAJQMBIBATGLJDTBNCPIFRDLRIJHRABBJGQAOLIKRLHDRIGERENNMJSDSSMESSTR'
    # s = 'SSMESSTR'
    # k = 2
    res = sc.characterReplacement3(s, k)
    print(res)
    res = sc.characterReplacement(s, k)
    print(res)
